package roman.algorithm;
// A binary, minimum heap.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class BinaryHeap<E extends Comparable<E>> {
	List<E> list = new ArrayList<E>();
	
	public BinaryHeap(){
		
	}
	
	public BinaryHeap(E[] tmp){
		for(E e:tmp)
			list.add(e);
		for(int start = (list.size()-1)/2; start >= 0 ; start --){
			siftDown(start,list.size()-1);
		}
	}
	
	public void siftDown(int start, int end){
		int root = start;
		int child;
		while (root*2+1 <= end){
			child = root*2 + 1;
			if (child < end && list.get(child).compareTo(list.get(child+1))>0)
				child++;
			if(list.get(root).compareTo(list.get(child))>0){
				Collections.swap(list, root, child);
				root = child;
			}
			else 
				return;
		}
	}
	
	public void siftUp(int i){
		int parent = (i - 1)/2;
		while(parent >= 0){
			if(list.get(i).compareTo(list.get(parent))<0){
				Collections.swap(list, i, parent);
				i = parent;
				parent = (parent - 1) / 2;
			}
			else
				break;
		}
	}
	
	public E remove(){
		E rtn = list.get(0);
		int size = list.size();
		Collections.swap(list, 0, size - 1);
		list.remove(size - 1);
		siftDown(0,list.size()-1);
		return rtn;
	}
	
	public void add(E e){
		list.add(e);
		siftUp(list.size()-1);
	}
	
	public int size(){
		return list.size();
	}
	
	public String toString(){
		String tmp = "";
		Iterator<E> it = list.iterator();
		while(it.hasNext())
			tmp += it.next() + " ";
		return tmp;
	}
}
